#include "stdafx.h"
#include "Solution.h"
#include <cassert>
#include <algorithm>

int Solution::maxCount(int m, int n, std::vector<std::vector<int>>& ops)
{
    return slnBruteForce(m, n, ops);
}

int Solution::slnBruteForce(int m, int n, std::vector<std::vector<int>>& ops)
{
    assert(m >= 1 && m <= 40000);
    assert(n >= 1 && n <= 40000);
    assert(ops.size() <= 10000);

    std::vector<std::vector<int>> datas(m, std::vector<int>(n, 0));
    ptrdiff_t opsCount = ops.size();
    // loop invariant:
    // [0, i) has done
    for (ptrdiff_t i = 0; i < opsCount ; i++) {
        // handling operation at index i
        const std::vector<int> &curOperation = ops[i];
        const int curA = curOperation[0];
        const int curB = curOperation[1];
        assert(curA >= 1 && curA <= m);
        assert(curB >= 1 && curB <= n);

        // do the operation
        // loop invariants: row
        // row of [0, row) has done
        for (ptrdiff_t row = 0; row < curA ; ++row) {
            // loop invariants: [0, col) has done
            for (ptrdiff_t col = 0; col < curB ; ++col) {
                datas[row][col] += 1;
            }
            // post condition: [0, curB) has done
        }
        // post condition: row of [0, curA) done
    }
    // post condition: [0, opsCount) has done

    int maxValCount = 0;
    int maxVal = datas[0][0];
    // loop invariants:
    // maxValCount: max value count in the searched range
    // [0, row) of row has searched
    for (ptrdiff_t row = 0; row < m; ++row) {
        // loop invariants:
        // column range [0, column) has done
        for (ptrdiff_t column = 0; column < n; ++column) {
            int value = datas[row][column];
            if (value == maxVal) {
                ++maxValCount;
            }
        }
        // post condition: [0, n) has done
    }
    // post condition: [0, m) of row has searched
    
    return maxValCount;
}

int Solution::slnFast(int m, int n, std::vector<std::vector<int>>& ops)
{
    if (ops.empty()) {
        return m * n;
    }

    int mina = ops[0][0];
    int minb = ops[0][1];

    // loop invariants:
    // [0, i) of ops has done
    // mina is the min row value in the done range
    // minb is the min column value in the done range
    for (ptrdiff_t i = 1; i < static_cast<ptrdiff_t>(ops.size()); ++i) {
        // we are handling ops[i]
        mina = std::min(mina, ops[i][0]);
        minb = std::min(minb, ops[i][1]);
    }
    // post condition: [0, ops.size()) of ops has done

    // result row range is [0, mina)
    // result col range is [0, minb)

    return mina * minb;
}
